package leetcode.leetcode_76;

import java.util.HashMap;

class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> sMap = new HashMap<>();
        HashMap<Character, Integer> tMap = new HashMap<>();
        int n = s.length();
        int m = t.length();
        for (int i = 0;i<m;i++){
            tMap.put(t.charAt(i),tMap.getOrDefault(t.charAt(i),0)+1);
        }
        String ans = new String();
        int left = 0,right = 0;
        while(right<n){
            sMap.put(s.charAt(right),sMap.getOrDefault(s.charAt(right),0)+1);
            while(check(sMap,tMap)){
                if (ans.equals("") || right-left+1<ans.length()){
                    ans = s.substring(left,right+1);
                }
                sMap.put(s.charAt(left),sMap.get(s.charAt(left))-1);
                if (sMap.get(s.charAt(left))==0){
                    sMap.remove(s.charAt(left));
                }
                left++;
            }
            right++;
        }
        return ans;
    }
    public boolean check(HashMap<Character, Integer> sMap, HashMap<Character, Integer> tMap){
        for (char c : tMap.keySet()){
            if (!sMap.containsKey(c) || sMap.get(c)<tMap.get(c)){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(new Solution().minWindow(s,t));
    }
}